package everyday;

/**
 * @author zhangmin
 * @create 2022-05-02 17:14
 * 完全平方数
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 *
 * 思路：
 * 1、dp[i]表示和为i的完全平方数的最少数量，dp[i]=Math.min(dp[i-j*j]):1<=j<=i*i
 * 2、四平方和定理：一个数的完全平和数量最大不会超过4
 * 当且仅当n！=(4^k)*(8*m+7)时，n可以被表示为最多四个正整数的平方和
 * 答案为1时，必定时n为完全平方数
 * 答案为2时，只需要枚举所有的a，判断n-a^2是否时完全平方数
 * 答案为3时，无法解决，但是可以使用排除法
 */
public class numSquares279 {
    //判断a是否是完全平方数
    public boolean isSquare(int a){
        int b= (int) Math.sqrt(a);
        return b*b==a;
    }
    //判断x是否满足(4^k)*(8*m+7)
    public boolean chack(int x){
         while (x%4==0){
             x/=4;
         }
         return x%8==7;
    }
    public int numSquares(int n) {
        if (isSquare(n)) return 1;
        if (chack(n)) return 4;
        for (int i = 1; i*i <=n ; i++) {
            int j=n-i*i;
            if (isSquare(j)){
                return 2;
            }
        }
        return 3;
    }
}
